/**
 * Created by L.jp
 * Description:在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
 * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
 * 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 *
 * User: 86189
 * Date: 2022-11-27
 * Time: 23:39
 */
public class Solution {
    public int maxValue(int[][] grid) {
        /*int row = grid.length;
        int column = grid[0].length;
        //dp[i][j]表示从grid[0][0]到grid[i - 1][j - 1]时的最大价值
        int[][] dp = new int[row + 1][column + 1];
        //i从1开始表示数组下标是从0开始访问的，当i=1时，i-1就是访问的第一个元素
        //对于dp数组来说如果i和j如果从1开始，那么利用到dp[i-1][j-1]就会越界，这样设计为了dp数组和grid数组都不越界
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= column; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[row][column];*/
        
        //优化，第i行的状态只与第i-1行的状态有关，所以可以采用滚动数组，思想就是压缩存储，每一行的数组循环更新直到当前位置为最大
        int n=grid.length;
        int m=grid[0].length;
        //dp[i]表示从0到i的最大价值
        int[] dp=new int[n+1];
        //dp数组从1开始，grid数组从0开始
        for(int i = 1; i <= n; i++){
            for(int j=1;j<=m;j++){
                //dp[j]一维数组每一个元素就是不断更新的，表示了从上一行和上一列演化来的值
                //数组滚动刷新
                dp[j]= Math.max( dp[j],dp[j-1] )+grid[i-1][j-1];
            }
        }
        return dp[n];
        
    }
}
